package com.sgffsg.learn.javalib.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: lmk
 * @date: 2024/4/17
 * @desc:
 */
public class QuickSort {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList();
        System.out.println("sort pre nums = " + Arrays.toString(nums));
        quickSort(nums, 0, nums.length - 1);
        System.out.println("sort end nums = " + Arrays.toString(nums));
        return list;
    }

    public static void main(String[] args) {
        char[] array = new char[]{'q', 'b'};
        String s = new String(array);
        StringBuilder sb = new StringBuilder(s);
        sb.deleteCharAt(2);
        s.toCharArray();
        Arrays.sort(array);


        QuickSort qs = new QuickSort();
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        System.out.println("sort pre nums = " + Arrays.toString(nums));
        qs.quickSort(nums, 0, nums.length - 1);
        System.out.println("sort end nums = " + Arrays.toString(nums));
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start > end) {
            return;
        }
        int ancher = nums[start];
        int left = start;
        int right = end;
        System.out.println("pre quickSort +start = " + start + ", end = " + end + ", left = " + left
                + ", right = " + right + ", nums = " + Arrays.toString(nums));
        while (left < right) {
            while (left < right && nums[right] >= ancher) {
                right--;
            }
            while (left < right && nums[left] <= ancher) {
                left++;
            }
            swap(nums, left, right);
            System.out.println("mid quickSort +start = " + start + ", end = " + end + ", left = " + left
                    + ", right = " + right + ", nums = " + Arrays.toString(nums));
        }
        System.out.println("end quickSort +start = " + start + ", end = " + end + ", left = " + left
                + ", right = " + right + ", nums = " + Arrays.toString(nums));
        swap(nums, start, left);
        quickSort(nums, start, left - 1);
        quickSort(nums, left + 1, end);
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
